package com.cwj.lab5.字符串.字典树;

import java.util.HashMap;
/**
 * 字典树（Trie tree）
 * 前缀树
 * */

//注意如果是只有ASCII码，那么就仅仅需要数组去充当哈希表即可，但如果是非常大的字符集那么就需要进行用哈希表
public class Trie {
    static class Node{
        boolean isEnd;
        HashMap<Character,Node>sonTable;

        public Node(boolean isEnd, HashMap<Character, Node> sonTable) {
            this.isEnd = isEnd;
            this.sonTable = sonTable;
        }

        public Node() {
            this.isEnd=false;
            this.sonTable=new HashMap<>();
        }
    }
    private Node root;
    private int sumWord;

    public Trie() {
        this.root=new Node(false,new HashMap<>());
        this.sumWord=0;
    }
    /** Inserts a word into the trie. */
    public void insert(String word) {
        Node nn=this.root,temp=null;
        for (int i = 0; i < word.length(); i++) {
            Character cc=word.charAt(i);
            if(!nn.sonTable.containsKey(cc)){
                nn.sonTable.put(cc,temp=new Node());
            }
            nn=nn.sonTable.get(cc);
        }
        nn.isEnd=true;
        this.sumWord+=1;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Node nn=this.find(word);
        if(nn==null){
            return false;
        }
        return nn.isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        Node nn=this.find(prefix);
        return nn!=null;
    }
    private Node find(String word){
        Node nn=this.root;
        for (int i = 0; i <word.length() ; i++) {
            Character cc=word.charAt(i);
            if(!nn.sonTable.containsKey(cc)){
                return null;
            }
            nn=nn.sonTable.get(cc);
        }
        return nn;
    }
}
